package crazy.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class ThreeLinkBinTree<T>
{
	public static class TreeNode
	{
		Object data;
		TreeNode left;
		TreeNode right;
		TreeNode parent;
		
		public TreeNode()
		{}
		
		public TreeNode(Object data)
		{
			this.data = data;
		}
		
		public TreeNode(Object data, TreeNode left, TreeNode right, TreeNode parent)
		{
			this.data = data;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}
	}
	
	private TreeNode root;
	
	public ThreeLinkBinTree()
	{
		this.root = new TreeNode();
	}
	
	public ThreeLinkBinTree(T data)
	{
		this.root = new TreeNode(data);
	}
	
	public TreeNode addNode(TreeNode parent, T data, boolean isLeft)//在哪个parent下面加node，是左还是右，node的值是什么
	{
		if (parent == null)
		{
			throw new RuntimeException("parent is null");
		}  
		
		if (isLeft && parent.left != null)
		{
			throw new RuntimeException("Left node has been added");
		}
		
		if (!isLeft && parent.right != null)
		{
			throw new RuntimeException("right node has been added");
		}
		
		TreeNode newNode = new TreeNode(data);
		if (isLeft)
		{
			parent.left = newNode;
		}
		else
		{
			parent.right = newNode;
		}
		
		newNode.parent = parent;
		return newNode;
		
	}
	
	public boolean empty()
	{
		return root.data == null;
	}
	
	public TreeNode root()
	{
		if (empty())
		{
			throw new RuntimeException("tree is null");
		}
		return root;
	}
	
	public T parent(TreeNode node)
	{
		if (node == null)
		{
			throw new RuntimeException("node is null");
		}
		return (T)node.parent.data;
	}
	
	public T leftChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException("parent is null");
		}
		
		return parent.left == null? null : (T)parent.left.data;
	}
	
	public T rightChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException("parent is null");
		}
		
		return parent.right == null? null : (T)parent.right.data;
	}
	
	public int deep()
	{
		return deep(root);
	}
	
	private int deep(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		
		if (node.left == null && node.right == null)
		{
			return 1;
		}
		else 
		{
			int leftDeep = deep(node.left);
			int rightDeep = deep(node.right);
			int max = leftDeep < rightDeep ? rightDeep : leftDeep;
			return max + 1;
		}
	}
	
	public List<TreeNode> preIterator()
	{
		return preIterator(root);
	}
	
	private List<TreeNode> preIterator(TreeNode node)
	{
		List<TreeNode> list = new ArrayList<TreeNode>();
		list.add(node);
		if (node.left != null)
		{
			list.addAll(preIterator(node.left));
		}
		if (node.right != null)
		{
			list.addAll(preIterator(node.right));
		}
		return list;
	}
	
	public List<TreeNode> inIterator()
	{
		return inIterator(root);
	}
	
	private List<TreeNode> inIterator(TreeNode node)
	{
		List<TreeNode> list = new ArrayList<TreeNode>();
		if (node.left != null)
		{
			list.addAll(inIterator(node.left));
		}
		list.add(node);
		if (node.right != null)
		{
			list.addAll(inIterator(node.right));
		}
		return list;
	}
	
	public List<TreeNode> postIterator()
	{
		return postIterator(root);
	}
	
	private List<TreeNode> postIterator(TreeNode node)
	{
		List<TreeNode> list = new ArrayList<TreeNode>();
		if (node.left != null)
		{
			list.addAll(postIterator(node.left));
		}
		if (node.right != null)
		{
			list.addAll(postIterator(node.right));
		}
		list.add(node);
		return list;
	}
	
	public List<TreeNode> breadthFirst()
	{
		Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
		List<TreeNode> list = new ArrayList<TreeNode>();
		
		if (root != null)
		{
			queue.offer(root);
		}
		
		while (!queue.isEmpty())
		{
			list.add(queue.peek());//Retrieves, but does not remove, the head of this queue
			TreeNode p = queue.poll();//Retrieves and removes the head of this queue
			if (p.left != null)
			{
				queue.offer(p.left);
			}
			if (p.right != null)
			{
				queue.offer(p.right);
			}
		}
		return list;
	}
}
